public class DAY0505 {
    //剑指 Offer 10- I. 斐波那契数列
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;
    }

    //剑指 Offer 10- II. 青蛙跳台阶问题
    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        int one = 1, two = 1;
        for (int i = 1; i < n; i++) {
            int tmp = (one + two) % 1000000007;
            one = two;
            two = tmp;
        }
        return two;
    }
}
